package LeetcodeTest_thirty_three;
//1642. 可以到达的最远建筑

public class furthestBuilding
{
    public static void main(String[] args)
    {
        int[] heights={4,12,2,7,3,18,20,3,19};
        int bricks=10;
        int ladders=2;
        System.out.println(Solutions.furthestBuilding(heights,bricks,ladders));
    }
}
class Solutions
{
    public static int ans=0;
    public static int furthestBuilding(int[] heights, int bricks, int ladders)
    {
        difs(0,heights,bricks,ladders);
        return ans;
    }
    public static void difs(int curr,int[] heights,int bricks,int ladders)
    {
        if(ans==heights.length-1)
            return;
        if(curr==heights.length-1||(bricks<heights[curr+1]-heights[curr]&&ladders<=0))
        {
            ans=Math.max(ans,curr);
            return;
        }
        if(heights[curr]>heights[curr+1])
            difs(curr+1,heights,bricks,ladders);
        else
        {
            if(bricks>=heights[curr+1]-heights[curr])
                difs(curr + 1, heights, bricks-(heights[curr+1]-heights[curr]), ladders);
            if(ladders>0)
                difs(curr + 1, heights, bricks, ladders-1);
        }
    }
}